The world has witnessed a tremendous growth in the deployment of wireless network technology driven by the need for ubiquitous service and rapid developments in telecommunications infrastructure. Mobile hosts such as notebook computers, featuring powerful CPUs and gigabytes of disk space are now easily affordable and becoming quite common in everyday life. At the same time, huge improvements have been made in wireless network hardware, and efforts are being made to integrate the two into a meaningful resource such as the Internet. We are witness to large scale proliferation of mobile computing and wireless technology in our day-to-day lives in the form of various hardware interfaces and technology devices, running numerous applications catering specifically to wireless technology. The use of cell phones and PDA's for mobile video conferencing, GPS based tracking systems and remote wireless sensor surveillance gives us an indication of the growth and proliferation of wireless technology in today's world.
The increased demand and usage of mobile devices, directly correlates to the inflated demand for mobile data and Internet services. The number of subscribers to wireless data services is predicted to reach 1.3 billion by end of 2004, and the number of wireless messages is sent per month is predicted to reach 244 billion by December 2004. But these devices and technology use the standard wireless network model of a base station, repeaters, access points, and wireless nodes. Oftentimes however mobile users will want to communicate in situations in which no fixed wired infrastructure is available, because it may not be possible to provide the necessary infrastructure or because the expediency of the situation does not permit this installation. The term, “ad hoc network” refers to such a collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration.
The history of ad hoc networks dates back to the DARPA radio packet network in 1972, which was primarily inspired by the efficiency of the packet switching technology, such as bandwidth sharing and store and forward routing, and its possible application in mobile wireless environment. But, it was not until the early 90's when research in the area of ad hoc networks gained significant momentum and widespread attention. This could be attributed to the surge in cheap availability of network hardware, the micro computer revolution, and the increasing number of applications that required an ad hoc network kind of setup. Some of the common applications for ad hoc networks include: conference halls, classrooms, search and rescue operations, vehicular communication, wireless surveillance and military operations. In an ad hoc network, every node acts as a router, and forwards packets towards the destination. It is a self-organized network where every node cooperates to provide connectivity and services.
MANET's or Mobile Ad hoc Networks have gained significant momentum as they are the solution for providing network services to mobile users at places where there is no infrastructure or an existing infrastructure needs wireless extensions. Wireless Mobile Ad Hoc Networks (MANETs) are very well suited to substitute current 802.11 Wireless Local Area Networks in practical implementations of semi-autonomous ground robots in Urban Search and Rescue (USAR) operations. MANETs are infrastructureless, self-configurable and self-forming networks with multi-hop capabilities, all very important features for USAR applications. However, node mobility may still cause partitions in the network topology, isolating robots from the network or even losing them, hindering the mission's success.
Urban Search and Rescue (USAR) focuses on locating life and resources in collapsed buildings or disaster sites affected by artificial or natural calamities. These disaster sites pose several situational hazards that drastically affect the efficiency of human rescue teams. Disaster sites are inherently unsafe, and movement inside these sites is extremely restricted due to the availability of only small or no entry voids to explore the rubble. Vibrations might further affect the foundation of the collapsed construction and could trigger a secondary collapse. Disaster sites are usually contaminated by water/sewage distribution systems, toxic gas spills, body fluids and other hazardous materials and gases. All of the above mentioned factors make it imperative to look for other effective means to carry out rescue operations. The use of mobile robots provides an effective alternative for improved efficiency in USAR operations. Due to smaller sizes and robust design, robots can explore disaster sites that pose numerous hazard threats and are not conducive for exploration by relief workers.
In USAR operations, and in general, in Safety, Security and Rescue (SSR) operations, a group of semi-autonomous ground vehicles is sent out to perform a determined mission under the guidance of the main controller, such as surveying a disaster site for life and resources. The success of the mission highly depends on the quality of the communication among the robots and the robots and the main controller. If communication is lost, the robots will lose contact with the main controller and the mission will likely fail. On the other hand, effective communication could actually enhance and increase the mission's success if it provided for a wider range of coverage, supported coordinated rescue operations and tele-operation, and guaranteed permanent connectivity despite network conditions and signal propagation effects. Communication among mobile robots and the main controller is currently known in the prior art to be achieved by using wireless local area networks (WLANs) based on the IEEE 802.11 standard.
The idea of using a WLAN of mobile robots in USAR operations has several drawbacks. First, WLANs require networking (access point) and energy (power outlet for access point) infrastructures, which are not readily available at disaster sites. Second, WLANs must be set up and configured, taking away precious search and rescue time. Third, communication performance is heavily affected by interferences, signal propagation effects, and the distance of the mobile nodes from the access point. 802.11 WLANs have an automatic fallback mechanism that reduces the transmission rate according to the quality of the transmission media. This feature makes the exploration of distant areas from the access point really difficult and risky. Finally, WLANs can't guarantee permanent connectivity. In USAR operations, mobile robots maneuvering the disaster site would need to maintain constant communication with a stationary controller, transmitting search findings and location information. The main controller is usually stationary and provides scope for tele-operation and analyzes findings of the robots to provide meaningful information to the relief workers. To ensure this constant communication with the main controller, the mobile robots and the main controller need to stay within the transmission range of the access point. Nodes moving beyond the transmission range of the access point are considered lost unless they use inherent position awareness protocols to trace route back to the main controller or work on an autonomous manner. Loss of robots not only produces financial loss but also jeopardize the mission's final success.
Most of the above mentioned issues could be resolved by forming a wireless mobile ad hoc network (MANET) of robots, where every node cooperates to provide connectivity and services. MANETs are self-organized and self-configured networks with multi-hop routing capabilities that operate without the need of any fixed infrastructure. Therefore, MANETs can be deployed and used rapidly, can drastically increase the area of coverage compared to WLANs, and can maintain communication with the main controller at all times in an easier manner, either by direct links or through intermediate nodes. MANETs may also reduce network congestion as routing remains distributed and the use of multi-hop routing may provide alternate routes for communication with the main controller.
Associated with these advantages and application possibilities are some inherent drawbacks that hold MANETs from being used as the communication platform of choice for semi-autonomous robots in USAR applications. For example, the nodes in an ad hoc network can move arbitrarily in a random direction and speed, which results in a very dynamic topology with frequent link breakages, disrupting communication among nodes and the main controller. Signal propagation effects in those harsh environments also cause communication problems. Nodes operating in ad hoc networks usually rely on batteries for energy, thus for these nodes energy-efficient protocols become a critical design criterion. Also, bandwidth utilization is another significant factor of concern, thus necessitating reduced routing overhead and good congestion control mechanisms.
By providing a constant communication link between the mobile robots and the main controller, it is ensured that the robots do not get lost. The term “node connectivity” is introduced here to denote the same. Node connectivity is defined as the ability of a node to continue or stop its mobility without breaking away from the network of nodes, while remaining in constant communication with the main controller. Forming an ad hoc network of the mobile robots and the main controller effectively addresses the issue of maximized area of coverage. By forming an ad hoc network, intermediate nodes act as a router forwarding packets towards the destination. By this method, robots continue their mobility beyond the transmission range of the main controller if an intermediate node exists through which it can establish a connection with the main controller. However, forming an ad hoc network of mobile robots does not address the issue of node connectivity. It is essential to ensure node connectivity in applications where loss of a node mobile robot in the case of urban and search and rescue operations could be detrimental to the performance of the system.
The vast majority of the research work done in the area of ad hoc networks has been focused on designing and developing routing protocols to address the issues of node mobility, overhead and energy efficiency. There has been an increased attention in developing routing protocols that consider the issue of link stability and the design of link stability based routing protocols, where routes to the destination are selected based on the strength of signals received from neighboring nodes or the duration for which the link has been active. It is well-known that there is no unique routing protocol that satisfies the requirements of all types of applications and rather, routing protocols are designed to optimize the performance of the application under consideration. For example, while an ad hoc network of laptops in a classroom presents low or no mobility and infrequent topology changes, the topology of an ad hoc network of nodes with random mobility in a military environment is highly dynamic. Similarly, the requirements for an ad hoc network of robots operating in urban search and rescue environments is different as robots have low but random mobility and work in unfriendly environments for signal propagation. The idea of applying ad hoc networking to a team of mobile robots is known in the art. The protocols known in the art include, Topology Broadcast based on Reverse-Path Forwarding (TBRPF), Ad hoc On-Demand Distance Vector (AODV), Associativity Based Routing (ABR), Temporally Ordered Routing Algorithm (TORA) and Zone Routing Protocol (ZRP). However, none of the prior art solutions are capable of guarantying node connectivity considering the energy available in the robots and the signal strength, a quite important characteristic for USAR applications where the final goal is to extend the area of coverage, avoid network partitions and loss of robots, and also extend the length of the mission under harsh signal propagation environments.
As illustrated in FIG. 1, a stationary main controller, and 6 mobile nodes (robots) are connected to form an ad hoc network. Robots 1, 2, 3 and 4 are within the transmission range of the main controller (denoted by a circle), while robots 5and 6 are outside its transmission range. This doesn't necessarily mean that robots 5 and 6 have lost their communication with main controller. For example, robot 6 can still communicate with the main controller through robot 2. Here robot 2 acts as a router, transmitting packets to and from robot 6. Similarly robot 5 can transmit its packets to the main controller through robot 3 or 4. But as it can be seen, robot 2 is moving outside the transmission range of the main controller. This not only breaks the communication link between robot 2 and the main controller, but also the link between robot 6 and the main controller, as robot 2 was serving as the link between these two nodes. None of the existing routing protocols current known in the art address this issue as illustrated and described with reference to FIG. 1. None of the prior art routing protocols is able to ensure that in addition to the existing demands of ad hoc networks such as node mobility, link stability, energy efficiency and reduced routing overhead, that the requirement for node connectivity is satisfied.
Accordingly, what is needed in the art is a system and method that is effective in assuring node connectivity in an ad hoc network.
However, in view of the prior art considered as a whole at the time the present invention was made, it was not obvious to those of ordinary skill in the pertinent art how the identified need could be fulfilled.